package newcoder_exp.bytedance;

import java.util.Arrays;
import org.junit.Test;

import linked.ListNode;
import utils.ArrayGenerator;

public class Bytedance5 {
    
    // 1. 反转
    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode post = head.next, temp, pre = head;
        while (post != null) {
            temp = post.next;
            post.next = head;
            head = post;
            post = temp;
        }
        pre.next = null;
        return head;
    }

    //1.1 递归反转
    public ListNode reverse2(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode last = recur(head);
        last.next = null;
        return res;
    }

    //不断返回尾结点
    ListNode res = null;
    public ListNode recur(ListNode head) {
        if (head.next == null) {
            res = head;
            return head;
        }
        ListNode last = recur(head.next);
        last.next = head;
        return head; //返回尾结点
    }

    @Test
    public void test1() {
        ListNode head = new ListNode(0), cur = head;
        head.next = new ListNode(1);
        cur = cur.next;
        cur.next = new ListNode(2);
        cur = cur.next;
        cur.next = new ListNode(3);cur = cur.next;
        cur.next = new ListNode(4);cur = cur.next;
        cur.next = new ListNode(5);

        head = reverse2(head);
        System.out.println(head);
    }


    //2. 快速
    public void quicksort(int[] nums, int left, int right) {
        if (left >= right) return;
        int pivot = partion(nums, left, right);
        quicksort(nums, left, pivot - 1);
        quicksort(nums, pivot + 1, right);
    }

    public int partion(int[] nums, int left, int right) {
        int lo = left - 1, rand = (int)(Math.random() * (right - left + 1)) + left;
        swap(nums, left, rand);
        int sentry = nums[left];
        while (lo < right) {
            if (nums[lo + 1] > sentry) {
                swap(nums, lo + 1, right--);
            } else {
                lo++;
            }
        }
        swap(nums, left, lo);
        return lo;
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    //2.2荷兰国旗 [等于k放中间]
    public void partion2(int[] nums, int k) {
        int lo = 0, len = nums.length, hi = len - 1;
        while (lo < hi) {
            if (nums[lo] < k) {
                lo++;
            } else{
                swap(nums, lo, hi--);
            }
        }
        System.out.println(lo);
        System.out.println(Arrays.toString(nums));
       hi = len - 1;
       lo++;
       while (lo < hi) {
           if (nums[hi] > k) {
               hi--;
           } else {
               swap(nums, lo++, hi);
           }
       }
    }

    @Test
    public void test3() {
        int[] nums = ArrayGenerator.getArray(20, 10);
        nums = new int[] {15, 5, 15, 9, 8, 2, 14, 9, 9, 5};
        System.out.println(Arrays.toString(nums));
        int k = nums[(int)(Math.random() * 10)];
        // System.out.println(k);
        partion2(nums, 9);
        System.out.println(Arrays.toString(nums));
    }

    @Test
    public void test() {
        for (int i = 0; i < 1000000; i++) {
            int[] nums = ArrayGenerator.getArray(100, 20);
            quicksort(nums, 0, nums.length - 1);
            String res1 = Arrays.toString(nums);
            Arrays.sort(nums);
            String res2 = Arrays.toString(nums);
            if (!res1.equals(res2)) {
                System.out.println(res1);
            }
        }
        System.out.println("nice");
    }
}
